package com.love.dynamicPlan;


/**
 * 746. 使用最小花费爬楼梯
 *
 * 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
 *
 * 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
 *
 * 请你计算并返回达到楼梯顶部的最低花费。
 *
 *
 *
 * 示例 1：
 *
 * 输入：cost = [10,15,20]
 * 输出：15
 * 解释：你将从下标为 1 的台阶开始。
 * - 支付 15 ，向上爬两个台阶，到达楼梯顶部。
 * 总花费为 15 。
 * 示例 2：
 *
 * 输入：cost = [1,100,1,1,1,100,1,1,100,1]
 * 输出：6
 * 解释：你将从下标为 0 的台阶开始。
 * - 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
 * - 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
 * - 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
 * - 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
 * - 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
 * - 支付 1 ，向上爬一个台阶，到达楼梯顶部。
 * 总花费为 6 。
 *
 */
public class CostStair {



    public static int Last(int[] cost){
        int N = cost.length;

        /**
         * dp[i] : 表示 到达 第 i 台阶，最少需要多少钱
         */
        int[] dp = new int[N + 1];

        dp[0]  = dp[1] = 0;


        for (int k = 2; k <= N ; k++) {
            dp[k] = Math.min(dp[k - 1] + cost[k - 1], dp[k - 2] + cost[k - 2]);
        }


        return dp[N];

    }


    public static void main(String[] args) {
        int[] num = {1,100,1,1,100,1,1,100,1};
//        int[] num = {10,15,20};

        System.out.println(Last(num));

    }


}
